import java.util.Arrays;

public class HashBucket_db {
    static class Node {
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    public int usedSize = 0;
    public Node[] array = new Node[10];
    public static final double DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 插入或更新键值对（仅支持key ≥ 0）
     * @param key 键（需≥0，否则视为无效）
     * @param val 值
     * @return 若key已存在，返回旧值；若为新插入，返回-1；若key无效，返回Integer.MIN_VALUE
     */
    public int push(int key, int val) {
        if (key >= 0) {
            // 计算索引（因key≥0，无需额外取绝对值）
            int index = key % array.length;
            Node cur = array[index];
            
            // 查找并更新已有key
            while (cur != null) {
                if (cur.key == key) {
                    int olderValue = cur.val;  // 修正变量命名
                    cur.val = val;
                    return olderValue;
                }
                cur = cur.next;
            }
            
            // 头插法插入新节点（简化冗余代码）
            Node node = new Node(key, val);
            node.next = array[index];  // 直接指向原头节点，无需临时变量cur
            array[index] = node;
            usedSize++;
            
            // 检查负载因子并扩容（修正方法名）
            if (getLoadFactor() > DEFAULT_LOAD_FACTOR) {
                resize();
            }
            return -1;  // 新节点插入成功
        }
        
        // 无效key（<0）返回特殊值，避免与有效场景混淆
        return Integer.MIN_VALUE;
    }

    /**
     * 扩容并重新哈希所有节点
     */
    private void resize() {
        Node[] newArray = new Node[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur != null) {
                Node curNext = cur.next;  // 修正变量命名（curN→curNext）
                // 计算新索引（因key≥0，无需取绝对值）
                int newIndex = cur.key % newArray.length;
                
                // 头插法插入新数组
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;
                cur = curNext;
            }
        }
        array = newArray;  // 简化赋值，去除冗余copy
    }

    /**
     * 计算负载因子
     * @return 当前负载因子（usedSize / array.length）
     */
    private double getLoadFactor() {  // 修正方法名和拼写
        return usedSize * 1.0 / array.length;
    }

    /**
     * 根据key获取值（仅支持key ≥ 0）
     * @param key 键（需≥0，否则返回-1）
     * @return 若key存在，返回对应值；否则返回-1
     */
    public int getValue(int key) {
        // 处理可能的负数key，避免负索引
        if (key < 0) {
            return -1;
        }
        int index = key % array.length;
        Node cur = array[index];
        
        while (cur != null) {
            if (cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;  // 未找到该key
    }
}